package com.study.algorithm.sort;

/**
 * 快速排序
 *
 * @Author HBZ
 * @Date 2020/7/18 22:51
 * @Description
 */
public class QuickSort {

    public static void sort(int[] arr, int low, int high) {
        int start = low;
        int end = high;
        int key = arr[start];
        while (end > start) {
            //从后往前比较
            while (end > start && key <= arr[end]) {
                //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                end--;
            }

            if (key > arr[end]) {
                int temp = arr[end];
                arr[end] = arr[start];
                arr[start] = temp;
                start++;
            }
            //从前往后比较
            while (end > start && key >= arr[start]) {
                //如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start++;
            }
            if (key < arr[start]) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
                end--;
            }

        }
        if (start > low) {
            sort(arr, low, start - 1);//左边序列。第一个索引位置到关键值索引-1
        }
        if (end < high) {
            sort(arr, end + 1, high);//右边序列。从关键值索引+1 到最后一个
        }

    }

    public static void main(String[] args) {
        int[] arr = {12, 20, 5, 16, 15, 1, 30, 40};
        sort(arr, 0, 7);
        System.out.println(args);
    }

}
